package _02_第二季._01_排序;

public class InsertionSort04<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        for(int begin=1;begin<array.length;++begin){
            insert(begin,search(begin));
        }
    }

    private int search(int index){
        int begin = 0;
        int end = index;
        while(begin<end){
            int mid = (end + begin) >> 1;
            if(cmp(array[index],array[mid])<0){
                end = mid;
            }else{
                begin = mid + 1;
            }
        }
        return begin;
    }

    private void insert(int source,int dest){
        E element = array[source];
        for(int i = source;i>dest;--i){
            array[source] = array[source - 1];
        }
        array[dest] = element;
    }
}
